UVa/12320 - Flight Control/12320.4.cpp

   1 // Ternary search and binary search. Accepted.
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 template <class T> string toStr(const T &x) { stringstream s; s << x; return s.str(); }
  25 template <class T> int toInt(const T &x) { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl
  30
  31 const double EPS = 1e-10;
  32
  33 int cmp(double x, double y = 0, double tol = EPS){
  34     return( x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 struct point {
  38     double x, y, z;
  39     point(){} point(double x, double y, double z) : x(x), y(y), z(z) {}
  40 };
  41
  42 int R[2], V[2];
  43 vector< point > P[2];
  44 double D[2][105];
  45
  46 inline double dist(const point &a, const point &b) {
  47     double dx = b.x - a.x, dy = b.y - a.y, dz = b.z - a.z;
  48     return sqrt(dx * dx + dy * dy + dz * dz);
  49 }
  50
  51 point positionAt(int p, double t) {
  52     double d = V[p] * t;
  53
  54     int i = upper_bound(D[p], D[p] + P[p].size(), d) - D[p] - 1;
  55     assert(i >= 0);
  56     double s = D[p][i];
  57     double distance = dist(P[p][i], P[p][i+1]);
  58     //assert(cmp(s + distance, d) >= 0);
  59     point ans = P[p][i];
  60     if (cmp(distance, 0.0) > 0) {
  61         double dx = P[p][i+1].x - P[p][i].x;
  62         double dy = P[p][i+1].y - P[p][i].y;
  63         double dz = P[p][i+1].z - P[p][i].z;
  64         ans.x += (d - s) * dx / distance;
  65         ans.y += (d - s) * dy / distance;
  66         ans.z += (d - s) * dz / distance;
  67     }
  68     //assert(cmp(s + dist(P[p][i], ans), d) == 0);
  69     return ans;
  70 }
  71
  72 double distanceAtTime(double t) {
  73     point p0 = positionAt(0, t);
  74     point p1 = positionAt(1, t);
  75     return dist(p0, p1);
  76 }
  77
  78 double touchAtTime(double t) {
  79     return cmp(distanceAtTime(t), 0.0 + R[0] + R[1]) <= 0;
  80 }
  81
  82 double findClosestTime(double left, double right) {
  83     // double bestTime = -1, bestDistance = 1e200;
  84     // for (double t = left; t <= right; t += 0.5) {
  85     //     double d = distanceAtTime(t);
  86     //     printf("At time %lf, distance is %lf\n", t, d);
  87     //     if (cmp(d, bestDistance) < 0) {
  88     //         bestDistance = d;
  89     //         bestTime = t;
  90     //     }
  91     // }
  92
  93     while (cmp(left, right) < 0) {
  94         double t1 = (2 * left + right) / 3;
  95         double t2 = (2 * right + left) / 3;
  96         double d1 = distanceAtTime(t1);
  97         double d2 = distanceAtTime(t2);
  98         if (d1 > d2) {
  99             left = t1;
 100         } else {
 101             right = t2;
 102         }
 103     }
 104     double ans = (left + right) / 2;
 105     //printf("Best is at time %lf, where distance is %lf\n", ans, distanceAtTime(ans));
 106     return ans;
 107 }
 108
 109 int main(){
 110     int casos; scanf("%d", &casos); while (casos--) {
 111         for (int p = 0; p < 2; ++p) {
 112             int k; assert(scanf("%d %d %d", &R[p], &V[p], &k) == 3);
 113             P[p].resize(k);
 114             for (int i = 0; i < k; ++i) {
 115                 scanf("%lf %lf %lf", &P[p][i].x, &P[p][i].y, &P[p][i].z);
 116             }
 117             P[p].push_back( point(0, 0, 0) );
 118         }
 119
 120         double totalTime = 1e100;
 121         for (int p = 0; p < 2; ++p) {
 122             D[p][0] = 0.0;
 123             for (int i = 1; i < P[p].size(); ++i) {
 124                 D[p][i] = D[p][i-1] + dist(P[p][i-1], P[p][i]);
 125             }
 126             totalTime = min(totalTime, D[p][P[p].size() - 1] / V[p]);
 127         }
 128         // D(totalTime);
 129         // point p1 = positionAt(0, totalTime);
 130         // point p2 = positionAt(1, totalTime);
 131         // printf("<%lf, %lf, %lf>\n", p1.x, p1.y, p1.z);
 132         // printf("<%lf, %lf, %lf>\n", p2.x, p2.y, p2.z);
 133         vector<double> times;
 134         for (int p = 0; p < 2; ++p) {
 135             double d = 0;
 136             times.push_back(0.0);
 137             for (int i = 0; i < P[p].size() - 1; ++i) {
 138                 d += dist(P[p][i], P[p][i+1]);
 139                 double t = d / V[p];
 140                 if (cmp(t, totalTime) <= 0) times.push_back(d / V[p]);
 141             }
 142         }
 143         sort(times.begin(), times.end());
 144         //For(i, 0, times.size() - 1) assert(cmp(times[i], times[i + 1]) <= 0);
 145         // for (int i = 0; i < times.size(); ++i) {
 146         //     printf("%lf ", times[i]);
 147         // }
 148         // puts("");
 149
 150         int ans = 0;
 151         for (int i = 0; i < times.size() - 1; ++i) {
 152             //printf("\nInterval from time (%lf, %lf):\n", times[i], times[i+1]);
 153             const double &t = times[i];
 154             if (touchAtTime(t)) {
 155                 //printf("They touch at time %lf, continuing.\n", t);
 156                 continue;
 157             }
 158             double closestTime = findClosestTime(t, times[i+1]);
 159             if (touchAtTime(closestTime)) {
 160                 ans++;
 161             }
 162         }
 163         if (touchAtTime(0.0)) ans++;
 164         printf("%d\n", ans);
 165     }
 166     return 0;
 167 }